#define _CRT_SECURE_NO_WARNINGS


#include"heap.h"


void heapInit(HP* hp)
{
	assert(hp);
	hp->data = NULL;
	hp->size = hp->capacity = 0;
}

void heapDestroy(HP* hp)
{
	assert(hp);
	free(hp->data);
	hp->data = NULL;
	hp->capacity = hp->size = 0;
}

void heapPush(HP* hp, heapDataType x)
{
	assert(hp);
	if (hp->capacity == hp->size)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		heapDataType* tmp = realloc(hp->data, sizeof(heapDataType*) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		hp->capacity = newcapacity;
		hp->data = tmp;
	}


	hp->data[hp->size] = x;
	hp->size++;

	adjustUp(hp->data, hp->size - 1);
}

void heapPop(HP* hp)
{
	assert(hp);
	assert(hp->size);

	swap(&hp->data[0], &hp->data[hp->size - 1]);

	hp->size--;

	adjustDown(hp->data, hp->size, 0);

}

void adjustUp(heapDataType* data, int child)
{
	assert(data);

	int parent = (child - 1) / 2;

	while (child != 0)
	{
		if (data[child] > data[parent])
		{
			swap(&data[child], &data[parent]);

			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void adjustDown(heapDataType* data, int size, int parent)
{
	assert(data);

	int child = parent * 2 + 1;

	while (child < size)
	{
		if (child + 1 < size && data[child + 1] > data[child])
		{
			child++;
		}

		if (data[child] > data[parent])	
		{
			swap(&data[child], &data[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}

}


void swap(heapDataType* child, heapDataType* parent)
{
	heapDataType tmp = *child;
	*child = *parent;
	*parent = tmp;
}

void heapPrint(HP* hp)
{
	assert(hp);
	//assert(hp->size);
	for (int i = 0; i < hp->size; i++)
	{
		printf("%d ", hp->data[i]);
	}
	printf("\n");
}